//写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 
//
// 
//
// 示例: 
//
// 输入: a = 1, b = 1
//输出: 2 
//
// 
//
// 提示： 
//
// 
// a, b 均可能是负数或 0 
// 结果不会溢出 32 位整数 
// 
// Related Topics 位运算 数学 👍 260 👎 0

package com.cute.leetcode.editor.cn;

import java.math.BigInteger;

public class BuYongJiaJianChengChuZuoJiaFaLcof {
    public static void main(String[] args) {
        Solution solution = new BuYongJiaJianChengChuZuoJiaFaLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 不用四则运算求两个数的和
         * 这是循环求的每一位，效率较低
         */
        public int add1(int a, int b) {
            StringBuilder s = new StringBuilder();
            boolean flag = false;
            for (int i = 0; i < 32; i++) {
                if ((a & 1) == 1 && (b & 1) == 1){
                    if (flag) s.append(1);
                    else {
                        flag = true;
                        s.append(0);
                    }
                }else if ((a & 1) == 1 || (b & 1)== 1){
                    if (flag) s.append(0);
                    else {
                        s.append(1);
                        flag = false;
                    }
                }else {
                    if (flag) {
                        s.append(1);
                        flag = false;
                    }else s.append(0);
                }
                a >>= 1;
                b >>= 1;
            }
            //TODO 这里不能使用Integer进行转换是因为最负数时会出现溢出
            return (int) Long.parseLong(s.reverse().toString(), 2);
        }

        /**
         * 使用异或求两个数的无进位和，使用与来求进位
         * sum = 无进位和 + 进位
         */
        public int add(int a, int b) {
            while (b != 0){// 只要有进位就再求和
                int c = (a & b) << 1;// 进位
                a ^= b;// 无进位和
                b = c;// 将进位给b
            }
            return a;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}